home *** CD-ROM | disk | FTP | other *** search
/ Day Cry / Day Cry CD.bin / oh_towns / taropyon / splib / splib.lzh / PRG / LHX / MAKETREE.C < prev    next >
C/C++ Source or Header  |  1992-12-30  |  3KB  |  189 lines
  1. /***********************************************************
  2.         maketree.c -- make Huffman tree
  3. ***********************************************************/
  4. #include    "lh386.h"
  5.  
  6. #include    "slidehuf.h"
  7.  
  8. #ifdef    __HIGHC__
  9. #    pragma    On(Print_reg_vars);
  10. #    pragma    On(Align_all_labels);
  11. #endif
  12.  
  13.  
  14. static short n = 0, heapsize = 0, heap[NC + 1];
  15. static ushort *freq, *sort = NULL;
  16. static uchar *len;
  17. static ushort len_cnt[17];
  18.  
  19. void        make_code(short n, uchar len[], ushort code[])
  20. {
  21.     ushort            weight[17];     /* 0x10000ul >> bitlen */
  22.     ushort            start[17];        /* start code */
  23.     REG ushort        j;
  24.     REG int            i;
  25.  
  26.     {
  27.         REG ushort        k;
  28.         j = 0;
  29.         k = 1 << (16 - 1);
  30.         for (i = 1; i <= 16; i++)
  31.         {
  32.             start[i] = j;
  33.             j += (weight[i] = k) * len_cnt[i];
  34.             k >>= 1;
  35.         }
  36.     }
  37.     start[0] = weight[0] = 0;
  38.     for (i = 0; i < n; i++)
  39.     {
  40.         j = len[i];
  41.         code[i] = start[j];
  42.         start[j] += weight[j];
  43.     }
  44. }
  45.  
  46. static void count_len(short i)
  47. /* call with i = root */
  48. {
  49.     static uchar depth = 0;
  50.  
  51.     if (i < n)
  52.         len_cnt[depth < 16 ? depth : 16]++;
  53.     else
  54.     {
  55.         depth++;
  56.         count_len(left[i]);
  57.         count_len(right[i]);
  58.         depth--;
  59.     }
  60. }
  61.  
  62. static void make_len(short root)
  63. {
  64.     REG int        i;
  65.     REG uint    cum;
  66.  
  67.     for (i = 0; i <= 16; i++)
  68.         len_cnt[i] = 0;
  69.     count_len(root);
  70.     cum = 0;
  71.     for (i = 16; i > 0; i--)
  72.     {
  73.         cum += len_cnt[i] << (16 - i);
  74.     }
  75. #if (UINT_MAX != 0xffff)
  76.     cum &= 0xffff;
  77. #endif
  78.     /* adjust len */
  79.     if (cum)
  80.     {
  81.         LHX_fprintf(stderr, "17");
  82.         len_cnt[16] -= cum;     /* always len_cnt[16] > cum */
  83.         do
  84.         {
  85.             for (i = 15; i > 0; i--)
  86.             {
  87.                 if (len_cnt[i])
  88.                 {
  89.                     len_cnt[i]--;
  90.                     len_cnt[i + 1] += 2;
  91.                     break;
  92.                 }
  93.             }
  94.         } while (--cum);
  95.     }
  96.     /* make len */
  97.     for (i = 16; i > 0; i--)
  98.     {
  99.         REG int        k;
  100.  
  101.         k = len_cnt[i];
  102.         while (k > 0)
  103.         {
  104.             len[*sort++] = i;
  105.             k--;
  106.         }
  107.     }
  108. }
  109.  
  110. static void downheap(short i)
  111. /* priority queue; send i-th entry down heap */
  112. {
  113.     REG short        j, k;
  114.  
  115.     k = heap[i];
  116.     while ((j = 2 * i) <= heapsize)
  117.     {
  118.         if (j < heapsize && freq[heap[j]] > freq[heap[j + 1]])
  119.             j++;
  120.         if (freq[k] <= freq[heap[j]])
  121.             break;
  122.         heap[i] = heap[j];
  123.         i = j;
  124.     }
  125.     heap[i] = k;
  126. }
  127.  
  128.  
  129. short        make_tree(short nparm, ushort freqparm[], uchar lenparm[], ushort codeparm[])
  130. /* make tree, calculate len[], return root */
  131. {
  132.     short    avail;
  133.  
  134.     n = nparm;
  135.     freq = freqparm;
  136.     len = lenparm;
  137.     avail = n;
  138.     heapsize = 0;
  139.     heap[1] = 0;
  140.     {
  141.         REG short    i;
  142.         for (i = 0; i < n; i++)
  143.         {
  144.             len[i] = 0;
  145.             if (freq[i])
  146.                 heap[++heapsize] = i;
  147.         }
  148.     }
  149.     if (heapsize < 2)
  150.     {
  151.         codeparm[heap[1]] = 0;
  152.         return heap[1];
  153.     }
  154.     {
  155.         REG short    i;
  156.         for (i = heapsize / 2; i >= 1; i--)
  157.             downheap(i);            /* make priority queue */
  158.     }
  159.     sort = codeparm;
  160.  
  161.     short    k;
  162.  
  163.     do
  164.     {
  165.         short    i, j;
  166.  
  167.                                 /* while queue has at least two entries */
  168.         i = heap[1];            /* take out least-freq entry */
  169.         if (i < n)
  170.             *sort++ = i;
  171.         heap[1] = heap[heapsize--];
  172.         downheap(1);
  173.         j = heap[1];            /* next least-freq entry */
  174.         if (j < n)
  175.             *sort++ = j;
  176.         k = avail++;            /* generate new node */
  177.         freq[k] = freq[i] + freq[j];
  178.         heap[1] = k;
  179.         downheap(1);            /* put into queue */
  180.         left[k] = i;
  181.         right[k] = j;
  182.     } while (heapsize > 1);
  183.     sort = codeparm;
  184.     make_len(k);
  185.     make_code(nparm, lenparm, codeparm);
  186.     return k;                    /* return root */
  187. }
  188.  
  189.